{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Coloring Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: btreeGameWinningMove"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树着色游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点&nbsp;<code>root</code>，树上总共有 <code>n</code> 个节点，且 <code>n</code> 为奇数，其中每个节点上的值从&nbsp;<code>1</code> 到&nbsp;<code>n</code>&nbsp;各不相同。</p>\n",
    "\n",
    "<p>最开始时：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>「一号」玩家从 <code>[1, n]</code>&nbsp;中取一个值&nbsp;<code>x</code>（<code>1 &lt;= x &lt;= n</code>）；</li>\n",
    "\t<li>「二号」玩家也从&nbsp;<code>[1, n]</code>&nbsp;中取一个值&nbsp;<code>y</code>（<code>1 &lt;= y &lt;= n</code>）且&nbsp;<code>y != x</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>「一号」玩家给值为&nbsp;<code>x</code>&nbsp;的节点染上红色，而「二号」玩家给值为&nbsp;<code>y</code>&nbsp;的节点染上蓝色。</p>\n",
    "\n",
    "<p>之后两位玩家轮流进行操作，「一号」玩家先手。每一回合，玩家选择一个被他染过色的节点，将所选节点一个 <strong>未着色 </strong>的邻节点（即左右子节点、或父节点）进行染色（「一号」玩家染红色，「二号」玩家染蓝色）。</p>\n",
    "\n",
    "<p>如果（且仅在此种情况下）当前玩家无法找到这样的节点来染色时，其回合就会被跳过。</p>\n",
    "\n",
    "<p>若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。</p>\n",
    "\n",
    "<p>现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个&nbsp;<code>y</code>&nbsp;值可以确保你赢得这场游戏，则返回&nbsp;<code>true</code> ；若无法获胜，就请返回 <code>false</code> 。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/08/01/1480-binary-tree-coloring-game.png\" style=\"width: 500px; height: 310px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>第二个玩家可以选择值为 2 的节点。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3], n = 3, x = 1\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点数目为 <code>n</code></li>\n",
    "\t<li><code>1 &lt;= x &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>n</code> 是奇数</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= n</code></li>\n",
    "\t<li>树中所有值 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-coloring-game](https://leetcode.cn/problems/binary-tree-coloring-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-coloring-game](https://leetcode.cn/problems/binary-tree-coloring-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,7,8,9,10,11]\\n11\\n3', '[1,2,3]\\n3\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "\n",
    "\n",
    "      def getNodeCount(tree):\n",
    "        # 获取树的节点数\n",
    "        if tree is None:\n",
    "          return 0\n",
    "\n",
    "        rs = 1\n",
    "        rs += getNodeCount(tree.left)\n",
    "        rs += getNodeCount(tree.right)\n",
    "        return rs\n",
    "      \n",
    "      def getNode(tree, val):\n",
    "        # 在树中获取指定数值的节点\n",
    "        if tree is None:\n",
    "          return None\n",
    "\n",
    "        if tree.val == val:\n",
    "          return tree\n",
    "        \n",
    "        node = getNode(tree.left, val)\n",
    "        if node is not None:\n",
    "          return node\n",
    "        node = getNode(tree.right, val)\n",
    "        if node is not None:\n",
    "          return node\n",
    "\n",
    "        return None\n",
    "\n",
    "      # 蓝色要超过一半才能赢\n",
    "      half = n // 2 + 1\n",
    "\n",
    "      xNode = getNode(root, x)\n",
    "      leftCount = getNodeCount(xNode.left)\n",
    "      if leftCount >= half:\n",
    "        return True\n",
    "      rightCount = getNodeCount(xNode.right)\n",
    "      if rightCount >= half:\n",
    "        return True\n",
    "      parentCount = n - leftCount - rightCount - 1\n",
    "      if parentCount >= half:\n",
    "        return True\n",
    "      return False\n",
    "      \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        c = [0, 0]\n",
    "        def helper(node):\n",
    "            if not node: \n",
    "                return 0\n",
    "            l, r = helper(node.left), helper(node.right)\n",
    "            if node.val == x:\n",
    "                c[0], c[1] = l, r\n",
    "            return l + r + 1\n",
    "        return helper(root) // 2 < max(max(c), n - sum(c) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsz = rsz = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz,rsz \n",
    "                lsz,rsz = ls,rs\n",
    "            return ls+rs+1\n",
    "        dfs(root)\n",
    "        #二号玩家可选的地方是，x的父节点，和左右子节点\n",
    "        m = max(n-(lsz+rsz+1),lsz,rsz)\n",
    "        if m*2>n:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsz = rsz = 0\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz, rsz\n",
    "                lsz, rsz = ls, rs\n",
    "            return ls + rs + 1\n",
    "        dfs(root)\n",
    "        return max(lsz, rsz, n - 1 - lsz - rsz) * 2 > n\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        \n",
    "        lsz = rsz = 0\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz, rsz\n",
    "                lsz, rsz = ls, rs\n",
    "            return ls + rs + 1\n",
    "        dfs(root)\n",
    "        return max(lsz, rsz, n - 1 - lsz - rsz) * 2 > n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val):\n",
    "        self.val = val\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: TreeNode, n: int, x: int) -> bool:\n",
    "        def count(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left =count(node.left)\n",
    "            right =count(node.right)\n",
    "            return left + right + 1\n",
    "        def find(node, val):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node.val == val:\n",
    "                return node\n",
    "            left = find(node.left, val)\n",
    "            right = find(node.right, val)\n",
    "            return left if left else right\n",
    "        node_x = find(root, x)\n",
    "        left = count(node_x.left)\n",
    "        right = count(node_x.right)\n",
    "        parent = n - left - right - 1\n",
    "        if max(left, right, parent) > n // 2:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        xl = 0\n",
    "        xr = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            if node.val == x:  # 查找x结点的位置\n",
    "                nonlocal xl,xr\n",
    "                xl,xr = l,r\n",
    "            return 1 + l + r\n",
    "        dfs(root)\n",
    "        half = (n+1)>>1\n",
    "        return max(xl,xr,n-xl-xr-1) >= half\n",
    "        # if xl >= half:\n",
    "        #     return True\n",
    "        # if xr >= half:\n",
    "        #     return True\n",
    "        # return n-xl-xr-1 >= half"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "         def dfs(root):\n",
    "            if root is None or root.val == x:\n",
    "                return root\n",
    "            return dfs(root.left) or dfs(root.right)\n",
    "\n",
    "         def count(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            return 1 + count(root.left) + count(root.right)\n",
    "\n",
    "         node = dfs(root)\n",
    "         l, r = count(node.left), count(node.right)\n",
    "         return max(l, r, n - l - r - 1) > n // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsz = rsz = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz,rsz\n",
    "                lsz,rsz = ls,rs\n",
    "            return ls + rs + 1\n",
    "        dfs(root)\n",
    "        return max(lsz,rsz,n - 1 -lsz - rsz) * 2 > n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        xNode = None\n",
    "\n",
    "        def getSubtreeSize(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            if node.val == x:\n",
    "                nonlocal xNode\n",
    "                xNode = node\n",
    "            return 1 + getSubtreeSize(node.left) + getSubtreeSize(node.right)\n",
    "\n",
    "        getSubtreeSize(root)\n",
    "        leftSize = getSubtreeSize(xNode.left)\n",
    "        if leftSize >= (n + 1) // 2:\n",
    "            return True\n",
    "        rightSize = getSubtreeSize(xNode.right)\n",
    "        if rightSize >= (n + 1) // 2:\n",
    "            return True\n",
    "        remain = n - leftSize - rightSize - 1\n",
    "        return remain >= (n + 1) // 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        xnode = None\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            if node.val == x:\n",
    "                nonlocal xnode\n",
    "                xnode = node\n",
    "            return 1 + dfs(node.left) + dfs(node.right)\n",
    "        dfs(root)\n",
    "        left = dfs(xnode.left)\n",
    "        if left >= (n+1)>>1:\n",
    "            return True\n",
    "        right = dfs(xnode.right)\n",
    "        if right >= (n+1)>>1:\n",
    "            return True\n",
    " \n",
    "        return n-left-right-1 >= (n+1)>>1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        #copy 0x3\n",
    "        lsz = rsz = 0\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs =dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz,rsz\n",
    "                lsz,rsz = ls,rs\n",
    "            return ls + rs + 1\n",
    "        dfs(root)\n",
    "        return max(lsz,rsz,n-1-lsz-rsz)*2>n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        xl = 0\n",
    "        xr = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            if node.val == x:  # 查找x结点的位置\n",
    "                nonlocal xl,xr\n",
    "                xl,xr = l,r\n",
    "            return 1 + l + r\n",
    "        dfs(root)\n",
    "        half = (n+1)>>1\n",
    "        return xl >= half or xr >= half or n-xl-xr-1 >= half\n",
    "        # if xl >= half:\n",
    "        #     return True\n",
    "        # if xr >= half:\n",
    "        #     return True\n",
    "        # return n-xl-xr-1 >= half"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        \n",
    "        cntLeft,cntRight=0,0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            ll = dfs(root.left)\n",
    "            lr = dfs(root.right)           \n",
    "            if root.val == x:\n",
    "                nonlocal cntLeft,cntRight\n",
    "                cntLeft = ll\n",
    "                cntRight = lr\n",
    "            return ll+lr+1\n",
    "        \n",
    "        dfs(root)\n",
    "        b = max(n-1-cntLeft-cntRight,cntLeft,cntRight)\n",
    "        return 2*b>n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        # y要想着色最多，只需选择x的父节点或某个子节点就行，所以分别计算这几个节点能染色的数量\n",
    "        self.x_left_sum = -1\n",
    "        self.x_right_sum = -1\n",
    "        def dfs(root):\n",
    "            if root == None:\n",
    "                return 0\n",
    "            left_sum = dfs(root.left)\n",
    "            right_sum = dfs(root.right)\n",
    "            if root.val == x:\n",
    "                self.x_left_sum = left_sum\n",
    "                self.x_right_sum = right_sum\n",
    "            return 1 + left_sum + right_sum\n",
    "        dfs(root)\n",
    "        remain = n-self.x_left_sum-self.x_right_sum-1\n",
    "        return remain > n//2 or self.x_left_sum > n//2 or self.x_right_sum > n//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsz = rsz = 0\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz, rsz\n",
    "                lsz, rsz = ls, rs\n",
    "            return ls + rs + 1\n",
    "        dfs(root)\n",
    "        return max(lsz, rsz, n - 1 - lsz - rsz) * 2 > n\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/binary-tree-coloring-game/solutions/2089813/mei-you-si-lu-yi-zhang-tu-miao-dong-pyth-btav/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        self.l_num = 0\n",
    "        self.r_num = 0\n",
    "        def dfs(root,x):\n",
    "            if not root: return 0\n",
    "            l=dfs(root.left,x)\n",
    "            r=dfs(root.right,x)\n",
    "            if root.val == x:\n",
    "                self.l_num=l\n",
    "                self.r_num=r\n",
    "            return l+r+1\n",
    "        dfs(root,x)\n",
    "        top = n-(self.l_num+self.r_num+1)\n",
    "        print(top,self.l_num,self.r_num)\n",
    "        return top>n/2 or self.l_num>n/2 or self.r_num>n/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "     # Helper function to count nodes in left and right subtrees\n",
    "        def count_nodes(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            return 1 + count_nodes(node.left) + count_nodes(node.right)\n",
    "        \n",
    "        # Helper function to find the node with given value\n",
    "        def find_node(node, value):\n",
    "            if not node:\n",
    "                return None\n",
    "            if node.val == value:\n",
    "                return node\n",
    "            left = find_node(node.left, value)\n",
    "            if left:\n",
    "                return left\n",
    "            return find_node(node.right, value)\n",
    "        \n",
    "        # Find the node with value x\n",
    "        x_node = find_node(root, x)\n",
    "        \n",
    "        # Count nodes in left, right, and parent subtrees\n",
    "        left_count = count_nodes(x_node.left)\n",
    "        right_count = count_nodes(x_node.right)\n",
    "        parent_count = n - left_count - right_count - 1\n",
    "        \n",
    "        # Check if there is a node that can guarantee a win for player 2\n",
    "        if left_count > n // 2 or right_count > n // 2 or parent_count > n // 2:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        \n",
    "        def dfs(cur) -> int:\n",
    "            if not cur: return 0\n",
    "            return dfs(cur.left)+dfs(cur.right)+1\n",
    "\n",
    "        l = r = 0\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if not cur: continue\n",
    "            if cur.val == x:\n",
    "                l = dfs(cur.left)\n",
    "                r = dfs(cur.right)\n",
    "                break\n",
    "            stack.append(cur.left)\n",
    "            stack.append(cur.right)\n",
    "        p = n-l-r-1\n",
    "        return 2*max([p, l, r]) > sum([p, l, r])\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        ans = 0\n",
    "        def dfs(node, x):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return 0\n",
    "            \n",
    "            left = dfs(node.left, x)\n",
    "            right = dfs(node.right, x)\n",
    "            if node.val==x:\n",
    "                ans = max(ans, left, right, n-left-right-1)\n",
    "            \n",
    "            return left+right+1\n",
    "        \n",
    "        dfs(root, x)\n",
    "        return ans>n/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        queue = deque([root])\n",
    "        node = None\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.val == x:\n",
    "                break\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "        \n",
    "        leftCount = 0\n",
    "        rightCount = 0\n",
    "        if node.left:\n",
    "            queueL = deque([node.left])\n",
    "            while queueL:\n",
    "                nodeL = queueL.popleft()\n",
    "                leftCount += 1\n",
    "                if nodeL.left:\n",
    "                    queueL.append(nodeL.left)\n",
    "                if nodeL.right:\n",
    "                    queueL.append(nodeL.right)\n",
    "        if node.right:\n",
    "            queueR = deque([node.right])\n",
    "            while queueR:\n",
    "                nodeR = queueR.popleft()\n",
    "                rightCount += 1\n",
    "                if nodeR.left:\n",
    "                    queueR.append(nodeR.left)\n",
    "                if nodeR.right:\n",
    "                    queueR.append(nodeR.right)\n",
    "        \n",
    "        TopCount = n - leftCount - rightCount - 1\n",
    "        return max(TopCount, leftCount, rightCount) > n // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        def dfs(root):\n",
    "            if root is None or root.val == x:\n",
    "                return root\n",
    "            return dfs(root.left) or dfs(root.right)\n",
    "\n",
    "        def count(root):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            return 1 + count(root.left) + count(root.right)\n",
    "\n",
    "        node = dfs(root)\n",
    "        l, r = count(node.left), count(node.right)\n",
    "        return max(l, r, n - l - r - 1) > n // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsz = rsz = 0\n",
    "\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz, rsz\n",
    "                lsz, rsz = ls, rs\n",
    "            return ls + rs + 1\n",
    "\n",
    "        dfs(root)\n",
    "        return max(lsz, rsz, n - 1 - lsz - rsz) * 2 > n\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        xl = 0\n",
    "        xr = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            if node.val == x:  # 查找x结点的位置\n",
    "                nonlocal xl,xr\n",
    "                xl,xr = l,r\n",
    "            return 1 + l + r\n",
    "        dfs(root)\n",
    "        half = (n+1)>>1\n",
    "        return max(xl,xr,n-xl-xr-1) >= half"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 二叉树着色游戏\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root, n, x):\n",
    "        def searchnode(node, v):                                                # 定位节点 \n",
    "            if node == None: \n",
    "                return None\n",
    "            if node.val == v: \n",
    "                return node\n",
    "            return searchnode(node.left, v) or searchnode(node.right, v) \n",
    "\n",
    "        def getcnt(node):                                                       # 计算节点下节点数\n",
    "            if node == None: return 0\n",
    "            return getcnt(node.left) + getcnt(node.right) + 1     \n",
    "\n",
    "        nodex = searchnode(root, x)                                             # 1.定位X\n",
    "        cntxl = getcnt(nodex.left)                                              # 2.计算cntxl, cntxr\n",
    "        cntxr = getcnt(nodex.right)\n",
    "        return ((cntxl + cntxr + 1)*2) < n or (cntxl*2) > n or (cntxr*2) > n    # 3.三种情形判断返回\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        xl = 0\n",
    "        xr = 0\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            l = dfs(node.left)\n",
    "            r = dfs(node.right)\n",
    "            if node.val == x:  # 查找x结点的位置\n",
    "                nonlocal xl,xr\n",
    "                xl,xr = l,r\n",
    "            return 1 + l + r\n",
    "        dfs(root)\n",
    "        half = (n+1)>>1\n",
    "        return max(xl,xr,n-xl-xr-1) >= half"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        left_res = 0\n",
    "        right_res = 0\n",
    "        another_res = 0\n",
    "    def getnodes(self, node: TreeNode, x: int):\n",
    "        # 返回每个node对应的节点数和 = self + left + right\n",
    "        if not node:\n",
    "            return 0\n",
    "        leftcnt = self.getnodes(node.left, x)\n",
    "        rightcnt = self.getnodes(node.right, x)\n",
    "        if node.val == x:\n",
    "            self.left_res = leftcnt\n",
    "            self.right_res = rightcnt\n",
    "            #直接return?\n",
    "        return leftcnt + rightcnt + 1\n",
    "\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        # 以x为根节点，重构成树，\n",
    "        # 遍历求三个方向的最大nodes数，假如一个方向>2个方向的nodes数和，则true\n",
    "        # 简化为： 求一个node的左子树的节点 + 右子树的节点， 剩下的总数 - (左 + 右 + 1)\n",
    "        if n <= 2:\n",
    "            return False\n",
    "        total_cnt = self.getnodes(root, x)\n",
    "        self.another_res = n - self.left_res - self.right_res - 1\n",
    "        #print(self.left_res, self.right_res, self.another_res)\n",
    "        max_nodes = max(self.left_res, self.right_res, self.another_res)\n",
    "        if max_nodes > n - max_nodes:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsz = rsz = 0\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz, rsz\n",
    "                lsz, rsz = ls, rs\n",
    "            return ls + rs + 1\n",
    "        dfs(root)\n",
    "        return max(lsz, rsz, n - 1 - lsz - rsz) * 2 > n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        ans_l = 0\n",
    "        ans_r = 0\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return 0\n",
    "            l = dfs(root.left)\n",
    "            r = dfs(root.right)\n",
    "            if root.val == x:\n",
    "                nonlocal ans_l,ans_r\n",
    "                ans_l = l\n",
    "                ans_r = r\n",
    "            return l+r+1\n",
    "        dfs(root)\n",
    "        return 2*max(n-ans_l-ans_r-1,ans_l,ans_r) > n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        cnt = 0\n",
    "        def traverse(root, x):\n",
    "            nonlocal n, cnt\n",
    "            if not root:\n",
    "                return 0\n",
    "            left = traverse(root.left, x)\n",
    "            right = traverse(root.right, x)\n",
    "            others = max(0, n - 1 - left - right)\n",
    "            if root.val == x:\n",
    "                cnt = max(others, left, right)\n",
    "            return left + right + 1\n",
    "        \n",
    "        traverse(root, x)\n",
    "        return cnt > n//2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        # 整个树可以划分为一号的左子树、右子树、和上方的其他节点区域\n",
    "        # 将问题抽象为选择一个区域，把区域中所有的点涂满\n",
    "        self.player1 = None\n",
    "        self.x = x\n",
    "        self.getTreeSize(root)\n",
    "        leftSize = self.getTreeSize(self.player1.left)\n",
    "        rightSize = self.getTreeSize(self.player1.right)\n",
    "        upSize = n - leftSize - rightSize - 1\n",
    "        maxSize = max([leftSize, rightSize, upSize])\n",
    "        return maxSize >= (n + 1) // 2\n",
    "\n",
    "    def getTreeSize(self, node: Optional[TreeNode]):\n",
    "        if not node:\n",
    "            return 0\n",
    "        elif node.val == self.x:\n",
    "           self. player1 = node\n",
    "        return 1 + self.getTreeSize(node.left) + self.getTreeSize(node.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "\n",
    "        node = self.dfs(root, x)\n",
    "\n",
    "        left_count = self.count(node.left)\n",
    "        right_count = self.count(node.right)\n",
    "\n",
    "        remaining_count = n - left_count - right_count - 1\n",
    "\n",
    "        # could optimize as lef_count > n/2 then return True\n",
    "        if left_count + right_count + 1 < remaining_count or left_count + remaining_count + 1 < right_count or right_count + remaining_count + 1 < left_count:\n",
    "            return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "    def count(self, root):\n",
    "        if root is None:\n",
    "            return 0\n",
    "        \n",
    "        return self.count(root.left) + self.count(root.right) + 1\n",
    "\n",
    "    def dfs(self, root, x):\n",
    "        if root is not None:\n",
    "            if root.val == x:\n",
    "                return root\n",
    "\n",
    "            ret = self.dfs(root.left, x)\n",
    "            if ret:\n",
    "                return ret\n",
    "            else:\n",
    "                return self.dfs(root.right, x)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsz = rsz = 0   ###lsz左子树，rsz右子树\n",
    "        def dfs(node:Optional[TreeNode]) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz,rsz   \n",
    "###内层函数可以读取外层函数的变量，但是如果在内部函数中尝试进行修改外部变量，且外部变量为不可变类型，则需要在变量前加nonlocal\n",
    "                lsz,rsz = ls,rs\n",
    "            return ls+ rs +1\n",
    "        dfs(root)\n",
    "        return max(lsz , rsz , n - 1 - lsz - rsz)*2 > n  ###左子树，右子树，父节点子树（2号玩家"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsz = rsz = 0\n",
    "\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "\n",
    "            if node is None:\n",
    "\n",
    "                return 0\n",
    "\n",
    "            ls = dfs(node.left)\n",
    "\n",
    "            rs = dfs(node.right)\n",
    "\n",
    "            if node.val == x:\n",
    "\n",
    "                nonlocal lsz, rsz\n",
    "\n",
    "                lsz, rsz = ls, rs\n",
    "\n",
    "            return ls + rs + 1\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return max(lsz, rsz, n - 1 - lsz - rsz) * 2 > n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsz = rsz = 0\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz, rsz\n",
    "                lsz, rsz = ls, rs\n",
    "            return ls + rs + 1\n",
    "        dfs(root)\n",
    "        return max(lsz, rsz, n - 1 - lsz - rsz) * 2 > n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "\n",
    "        def dfs1(node: TreeNode) -> TreeNode:\n",
    "            if not node:\n",
    "                return\n",
    "            if node.val == x:\n",
    "                return node\n",
    "            return dfs1(node.left) or dfs1(node.right)\n",
    "\n",
    "        def dfs2(node: TreeNode) -> int:\n",
    "            if not node:\n",
    "                return 0\n",
    "            return dfs2(node.left) + dfs2(node.right) + 1\n",
    "        \n",
    "        x = dfs1(root)\n",
    "\n",
    "        left_num = dfs2(x.left)\n",
    "        if left_num >= (n + 1) // 2:\n",
    "            return True\n",
    "        right_num = dfs2(x.right)\n",
    "        if right_num >= (n + 1) // 2:\n",
    "            return True\n",
    "        return n - left_num - right_num - 1 >= (n + 1) // 2\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        stack=[root]\n",
    "        mid=None\n",
    "        while stack:\n",
    "            mid=stack.pop()\n",
    "            if mid.val==x:\n",
    "                break\n",
    "            else:\n",
    "                if mid.left:\n",
    "                    stack.append(mid.left)\n",
    "                if mid.right:\n",
    "                    stack.append(mid.right)\n",
    "        def find(mid):\n",
    "            stack=[mid]\n",
    "            i=0\n",
    "            while stack:\n",
    "                mid=stack.pop()\n",
    "                i+=1\n",
    "                if mid.left:\n",
    "                    stack.append(mid.left)\n",
    "                if mid.right:\n",
    "                    stack.append(mid.right)\n",
    "            return i\n",
    "        left=right=0\n",
    "        if mid.left:\n",
    "            left=find(mid.left)\n",
    "        if mid.right:\n",
    "            right=find(mid.right)\n",
    "        if max(left,right,n-left-right-1)*2>n:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = False\n",
    "\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        self.traverse(root, n, x)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, root, n, x):\n",
    "        if not root:\n",
    "            return 0\n",
    "        left = self.traverse(root.left, n, x)\n",
    "        right = self.traverse(root.right, n, x)\n",
    "        if x == root.val and (left > n / 2 or right > n / 2 or n - left - right-1 > n / 2):\n",
    "            self.res = True\n",
    "        return left + right + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def btreeGameWinningMove(self, root, n, x):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type n: int\n",
    "        :type x: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        self.x_address = 0\n",
    "        \n",
    "        def dfs(node): #找x对应的节点的地址\n",
    "            if not node:\n",
    "                return \n",
    "            if node.val == x:\n",
    "                self.x_address = node\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        \n",
    "        def cnt_node_in_subtree(node): #统计以一个节点为根节点的子树里结点的个数\n",
    "            if not node:\n",
    "                return 0\n",
    "            return 1 + cnt_node_in_subtree(node.left) + cnt_node_in_subtree(node.right)\n",
    "        \n",
    "        if root.val == x:     \n",
    "            return cnt_node_in_subtree(root.left) != cnt_node_in_subtree(root.right)\n",
    "        else:\n",
    "            x_cnt = cnt_node_in_subtree(self.x_address)\n",
    "            total_cnt = cnt_node_in_subtree(root) \n",
    "            left_cnt = cnt_node_in_subtree(self.x_address.left)\n",
    "            right_cnt = cnt_node_in_subtree(self.x_address.right)\n",
    "            return x_cnt < total_cnt - x_cnt or left_cnt > total_cnt - left_cnt or right_cnt > total_cnt - right_cnt\n",
    "            # 分别对应 选父节点， 选左孩子，选右孩子"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        def dfs(node)->int:\n",
    "            if node == None:\n",
    "                return 0\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lSize,rSize\n",
    "                lSize = left\n",
    "                rSize = right\n",
    "            return left+right+1\n",
    "        lSize,rSize = 0,0\n",
    "        dfs(root)\n",
    "        m = max(lSize, rSize, n-1-lSize-rSize)\n",
    "        if 2*m > n:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        self.count = 0\n",
    "        def coun(root: Optional[TreeNode],x):\n",
    "            if root.val != x:\n",
    "                self.count = self.count + 1\n",
    "                if root.left :\n",
    "                    coun(root.left, x)\n",
    "                if root.right :\n",
    "                    coun(root.right, x)\n",
    "            else:\n",
    "                self.froot = root\n",
    "        coun(root,x)\n",
    "        count1 = self.count\n",
    "        self.count = 0\n",
    "        if self.froot.left:\n",
    "            coun(self.froot.left, x)\n",
    "            count2 = self.count\n",
    "            self.count = 0\n",
    "        else:\n",
    "            count2 = 0\n",
    "        if self.froot.right:\n",
    "            coun(self.froot.right, x)\n",
    "            count3 = self.count\n",
    "            self.count = 0\n",
    "        else:\n",
    "            count3 = 0\n",
    "\n",
    "        list = sorted([count1,count2,count3])\n",
    "\n",
    "        if list[-1] > list[0]+list[1]+1:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        \n",
    "        def dfs(cur) -> int:\n",
    "            if not cur: return 0\n",
    "            return dfs(cur.left)+dfs(cur.right)+1\n",
    "\n",
    "        l = r = 0\n",
    "        s = dfs(root)\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if not cur: continue\n",
    "            if cur.val == x:\n",
    "                l = dfs(cur.left)\n",
    "                r = dfs(cur.right)\n",
    "                break\n",
    "            stack.append(cur.left)\n",
    "            stack.append(cur.right)\n",
    "        p = s-l-r-1\n",
    "        return 2*max([p, l, r]) > sum([p, l, r])\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsz = rsz = 0\n",
    "        def dfs(node: Optional[TreeNode]) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz, rsz\n",
    "                lsz, rsz = ls, rs\n",
    "            return ls + rs + 1\n",
    "        dfs(root)\n",
    "        return max(lsz, rsz, n - 1 - lsz - rsz) * 2 > n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsz = 0\n",
    "        rsz = 0\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            ls = dfs(node.left)\n",
    "            rs = dfs(node.right)\n",
    "            if node.val == x:\n",
    "                nonlocal lsz,rsz\n",
    "                lsz,rsz = ls,rs\n",
    "            return ls+rs+1\n",
    "        dfs(root)\n",
    "        return max(lsz,rsz,n-1-lsz-rsz)*2 > n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        queue = deque()\n",
    "        queue.append(root)\n",
    "        cur = None\n",
    "        while queue:\n",
    "            a = queue.popleft()\n",
    "            if a.val == x:\n",
    "                queue.clear()\n",
    "                cur = a\n",
    "                break\n",
    "            left = a.left\n",
    "            right = a.right\n",
    "            if left:\n",
    "                queue.append(left)\n",
    "            if right:\n",
    "                queue.append(right)\n",
    "        cntLeft = 0\n",
    "        cntRight = 0\n",
    "        if cur.left:\n",
    "            queue.append(cur.left)\n",
    "            cntLeft+=1\n",
    "            while queue:\n",
    "                a = queue.popleft()\n",
    "                left = a.left\n",
    "                right = a.right\n",
    "                if left:\n",
    "                    queue.append(left)\n",
    "                    cntLeft+=1\n",
    "                if right:\n",
    "                    queue.append(right)     \n",
    "                    cntLeft+=1\n",
    "        if cur.right:\n",
    "            queue.append(cur.right)\n",
    "            cntRight+=1\n",
    "            while queue:\n",
    "                a = queue.popleft()\n",
    "                left = a.left\n",
    "                right = a.right\n",
    "                if left:\n",
    "                    queue.append(left)\n",
    "                    cntRight+=1\n",
    "                if right:\n",
    "                    queue.append(right)     \n",
    "                    cntRight+=1                   \n",
    "\n",
    "        b = max(n-1-cntLeft-cntRight,cntLeft,cntRight)\n",
    "        return 2*b>n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:\n",
    "        lsize=rsize=0\n",
    "        def dfs(node):\n",
    "            if not node:return 0\n",
    "            ll=dfs(node.left)#左子树节点个数\n",
    "            rr=dfs(node.right)#右子树节点个数\n",
    "            if node.val==x:\n",
    "                nonlocal lsize,rsize\n",
    "                lsize=ll\n",
    "                rsize=rr\n",
    "\n",
    "            #node这棵树的节点个数是ll+rr+1\n",
    "            return ll+rr+1\n",
    "        dfs(root)\n",
    "        return max(lsize,rsize,n-lsize-rsize-1)>n//2"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
